package code201_300.code50_60;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 *
 * 叶子节点 是指没有子节点的节点。
 *
 * 输入：root = [1,2,3,null,5]
 * 输出：["1->2->5","1->3"]
 *
 * 输入：root = [1]
 * 输出：["1"]
 */
public class _257binaryTreePaths {

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode node;
        StringBuilder temp = new StringBuilder();

        while (stack.size()!=0){
            node = stack.pop();
            if(node.left!=null)stack.push(node.left);
            if(node.right!=null)stack.push(node.right);
            if(node.left==null&&node.right==null){
                temp.append(node.val);
                list.add(new String(temp));
                temp = new StringBuilder();
            }else {
                temp.append(node.val+"->");
            }
        }
        return list;
    }

    /**
     * 首先用递归方法实现
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.7 MB     * , 在所有 Java 提交中击败了     * 31.73%     * 的用户
     * @param root
     * @return
     */
    public List<String> binaryTreePaths1(TreeNode root) {
        List<String> path = new ArrayList<>();
        constructPaths(root,"",path);
        return path;
    }

    private void constructPaths(TreeNode root, String path, List<String> paths) {
        if(root!=null){
            StringBuffer pathBuffer = new StringBuffer(path);
            pathBuffer.append(Integer.toString(root.val));
            if(root.left == null && root.right == null){
                paths.add(pathBuffer.toString());
            }else {
                pathBuffer.append("->");
                constructPaths(root.left,pathBuffer.toString(),paths);
                constructPaths(root.right,pathBuffer.toString(),paths);
            }
        }
    }

}
